/**
 * 二叉树的最近公共祖先
 * @param root 
 * @param p 
 * @param q 
 */
const lowestCommonAncestor = (root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null => {
    if (root == null) return null
    
    // 如果左子树就是根, 返回
    if (root === p) return p
    // 如果右子树就是根, 返回
    if (root === q) return q

    // 往左子树找
    const left = lowestCommonAncestor(root.left, p, q)

    // 往右子树找
    const right = lowestCommonAncestor(root.right, p, q)

    // 左右都找到, 说明p和q分割在两边
    if (left !== null && right !== null) return root;

    return left === null ? right : left;
};